﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.InteropServices;
using System.Text;

using Util;

namespace Algorithm.Sort
{
    public class QuickSorter<T> : SorterBase<T>
    {
        [AlgorithmVariation]
        public void Sort(T[] elements, IComparer<T> comparer)
        {
            QuickSort(elements, 0, elements.Length - 1, comparer);
        }

        private static void QuickSort(T[] list, int left, int right, IComparer<T> comparer)
        {
            if (left >= right)
            {
                return;
            }

            int low = left + 1;
            int high = right;

            // Compares the only two elements and return.
            if (low == high)
            {
                if (comparer.Compare(list[left], list[right]) > 0)
                {
                    Swap(list, left, right);
                }

                return;
            }

            T pivot = list[left];

            while (low < high)
            {
                while (high > left && comparer.Compare(list[high], pivot) >= 0)
                {
                    high--;
                }

                while (low < high && comparer.Compare(list[low], pivot) < 0)
                {
                    low++;
                }

                if (low < high)
                {
                    Swap(list, low, high);
                }
            }

            list[left] = list[high];
            list[high] = pivot;

            QuickSort(list, left, high - 1, comparer);
            QuickSort(list, high + 1, right, comparer);
        }
    }
}
